// https://www.lintcode.com/problem/connected-component-in-undirected-graph/description

/**
 * Definition for Undirected graph.
 * struct UndirectedGraphNode {
 *     int label;
 *     vector<UndirectedGraphNode *> neighbors;
 *     UndirectedGraphNode(int x) : label(x) {};
 * };
 */
// 法一：并查集
// class UnionFind 
// {
//     public:
//     // int* father;
//     map<int, int> father;
//     UnionFind(vector<UndirectedGraphNode*> nodes)
//     {
//         // father = new int[n];
//         for (auto n: nodes)
//         {
//             father[n->label] = n->label;
//         }
//     }
//     int find(int n)
//     {
//         if (father[n] == n)
//             return n;
//         else
//             return father[n] = find(father[n]);
//     }
//     void connect(int a, int b)
//     {
//         int fatherA = find(a);
//         int fatherB = find(b);
//         if (fatherA != fatherB)
//             father[fatherA] = fatherB;
//     }
// };
// class Solution {
// public:
//     /*
//      * @param nodes: a array of Undirected graph node
//      * @return: a connected set of a Undirected graph
//      */
//     vector<vector<int>> connectedSet(vector<UndirectedGraphNode*> nodes) {
//         vector<vector<int>> res;
//         int n = nodes.size();
//         UnionFind uf(nodes);
       
//         for (UndirectedGraphNode* un: nodes)
//         {
//             for (UndirectedGraphNode* neib: un->neighbors)
//             {
//                 if (uf.find(neib->label) != uf.find(un->label)) //注意判断，否则就有环了
//                 {
//                     uf.connect(neib->label, un->label);
//                 }
//             }
//         }
//         map<int, vector<int>> tmp;
//         for (auto n: nodes)
//         {
//             int father = uf.find(n->label);
//             tmp[father].push_back(n->label);
//         }
//         for (auto t: tmp)
//         {
//             res.push_back(t.second);
//         }
//         return res;
//     }
// };


// 法二：bfs
// class Solution {
// public:
//     /*
//      * @param nodes: a array of Undirected graph node
//      * @return: a connected set of a Undirected graph
//      */
//     vector<vector<int>> connectedSet(vector<UndirectedGraphNode*> nodes) {
//         int n = nodes.size();
//         map<int, bool> visited;
//         vector<vector<int>> res;
//         for (int i = 0; i < nodes.size(); ++i)
//         {
//             if (visited[nodes[i]->label])
//                 continue;
//             queue<UndirectedGraphNode*> q;
//             vector<int> tmp;
//             q.push(nodes[i]);
//             visited[nodes[i]->label] = true;
//             while (!q.empty())
//             {
//                 UndirectedGraphNode* tmpNode = q.front();
//                 q.pop();
//                 tmp.push_back(tmpNode->label);
//                 for (UndirectedGraphNode* nn: tmpNode->neighbors)
//                 {
//                     if (!visited[nn->label])
//                     {
//                         q.push(nn);
//                         visited[nn->label] = true;
//                     }
//                 }
//             }
//             sort(tmp.begin(), tmp.end());
//             res.push_back(tmp);
//         }
//         return res;
//     }
// };


// 法三：dfs
class Solution {
public:
    /*
     * @param nodes: a array of Undirected graph node
     * @return: a connected set of a Undirected graph
     */
    void dfs(UndirectedGraphNode* node, vector<int>& res, map<int, bool>& visited)
    {
        // if (visited[node->label])
        // {
        //     return;
        // }
        for (UndirectedGraphNode* n: node->neighbors)
        {
            if (!visited[n->label])
            {
                res.push_back(n->label);
                visited[n->label] = true;
                dfs(n, res, visited);
            }
        }
    }
    vector<vector<int>> connectedSet(vector<UndirectedGraphNode*> nodes) {
        vector<vector<int>> res;
        map<int, bool> visited;
        for (UndirectedGraphNode* n: nodes)
        {
            if (!visited[n->label])
            {
                vector<int> tmp;
                tmp.push_back(n->label); //注意别丢了
                visited[n->label] = true;
                dfs(n, tmp, visited);
                sort(tmp.begin(), tmp.end());
                res.push_back(tmp);
            }
        }
        return res;
    }
};